package oj.oj_236;

import oj.oj_144.TreeNode;

/**
 * 二叉树的最近公共祖先
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 */
public class Solution {
    private boolean containsNode(TreeNode root, TreeNode targetNode) {
        if (root == null) {
            return false;
        }

        if (root == targetNode) {
            return true;
        }

        return containsNode(root.left, targetNode)
                || containsNode(root.right, targetNode);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // p 和 q 在 root 树中
        // 断言 root != null
        // 这里没有判断过 root == null 的情况，有问题么？

        if (root == p || root == q) {
            return root;
        }

        // 判断情况
        boolean pInLeft = containsNode(root.left, p);   // p 在不在左子树中
        boolean qInLeft = containsNode(root.left, q);   // q 在不在左子树中

        // 隐含前提：p 和 q 一定是树中的结点
        // p、q 只有三种可能：要么是根（这个我们排除了）
        // 只有左子树和右子树两种情况
        // 所以，如果不在左子树，一定在右子树
        // 所以没必要再去找右子树了

        if (pInLeft == true && qInLeft == true) {
            // 说明 p、q 都在左子树
            // 两个结点都在子树中，才继续递归，断言 root.left != null
            return lowestCommonAncestor(root.left, p, q);
        }

        if (pInLeft == false && qInLeft == false) {
            // 说明 p、q 都在右子树
            // 两个结点都在子树中，才继续递归，断言 root.right != null
            return lowestCommonAncestor(root.right, p, q);
        }

        // 说明一个左，一个右，谁左谁右不关心了
        // pInLeft == true && qInLeft == false
        // pInLeft == false && qInLeft == true
        return root;
    }
}
